# Copyright 2017 Google Inc.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""Convert "pyparsed" CLIF PYTD IR to CLIF AST proto.

Use
  p = Postprocessor()
  p.Translate(file_object) to get CLIF AST proto generated from CLIF PYTD text.

In case of errors it will raise an exception. Possible exceptions are:
  pyparsing.ParseFatalException - grammar error in input text
  NameError - wrong naming (usually duplicate names)
  SyntaxError - wrong construct or statement usage
"""

import codecs
import contextlib
import os
import pickle
import re
import sys

from clif.protos import ast_pb2
from clif.python import ast_manipulations
from clif.python import pytd_parser

CLIF_USE = re.compile(r'// *CLIF:? +use(?P<priority>2*)'
                      r' +`(?P<cname>.+)` +as +(?P<pyname>[\w.]+)')
CLIF_INIT = re.compile(r'// *CLIF:? +init_module +(?P<cpp_statement>.+)')
CLIF_MACRO = re.compile(r'// *CLIF:? +macro +(?P<name>.+) +(?P<def>.+)$')
CLIF_INCLUDE = re.compile(r'// *CLIF:? +include +"(?P<path>[^"]+)"')
KEEP_GIL_DECORATOR = 'do_not_release_gil'


def _read_include(input_stream, fname, prefix, typetable, capsules, interfaces,
                  extra_init):
  """Reads a C++ .h file generated by CLIF to check wrapper information."""
  for s in input_stream:
    use = CLIF_USE.match(s)
    if use:
      priority = 2 if use.group('priority') == '2' else 0
      cname = use.group('cname')
      cname = use.group('cname')
      pyname = use.group('pyname')
      if pyname.endswith('.'):  # Like in a normal English sentence.
        pyname = pyname[:-1]
      if not (cname and pyname):
        raise SyntaxError('Invalid "use" pragma in "%s": %s' % (fname, s))
      pyname = prefix + pyname
      if pyname in capsules:
        raise NameError('C++ type "%s" already wrapped as capsule by name %s'
                        % (cname, pyname))
      if typetable.has_type(pyname) and cname.endswith('*'):
        raise NameError('C++ type "%s" already wrapped by name %s'
                        % (cname, pyname))

      existing_pyname = typetable.find_pyname_for_cpp_type(cname)
      if existing_pyname:
        raise NameError('C++ type {!r} already wrapped by name {!r}'.format(
            cname, existing_pyname))
      if cname.endswith('*'):
        capsules[pyname] = cname
      else:
        typetable.add_type(priority, pyname, cname)
      continue
    init = CLIF_INIT.match(s)
    if init:
      extra_init.append(init.group('cpp_statement'))
      continue
    include = CLIF_INCLUDE.match(s)
    if include:
      yield include.group('path')
      continue
    macro = CLIF_MACRO.match(s)
    if macro:
      name = macro.group('name')
      s = macro.group('def').replace(r'\n', '\n').encode('utf-8')
      try:
        sysver, ppver, src = pickle.loads(s)
      except Exception:  # pylint: disable=broad-except
        raise ImportError('Macro %s loading error' % name)
      if sysver != sys.hexversion or ppver != pytd_parser.version:
        raise ValueError('Interface name "%s" from file %s is from '
                         'incompatible version (%s, %s)'
                         % (name, fname, sysver, ppver))
      if name in interfaces:
        raise NameError('Interface name "%s" from file %s already used'
                        % (name, fname))
      interfaces[name] = src + (False,)
      continue


class Postprocessor:
  """Process parsed IR."""

  def __init__(self, config_headers=None, include_paths=('.',), preamble=''):
    self._options = []
    self._names = {}  # Keep name->FQN for all 'from path import' statements.
    self._capsules = {}   # Keep raw pointer names (pytype -> cpptype).
    self._typenames = {}  # Keep typedef aliases (pytype -> type_ir).
    self._typetable = _TypeTable()
    self._macros = {}  # Keep interfaces (name -> (num_args, subtree, local)).
    self._scan_includes = config_headers or []
    self._include_paths = include_paths
    self._preamble = preamble
    self.source = None
    # _macro_values [actual, param, values] only set in _class that
    # has implements MACRO<actual, param, values>.
    self._macro_values = []

  def is_pyname_known(self, name):
    return (name in self._capsules or
            self._typetable.has_type(name) or
            name in self._typenames)

  def check_known_name(self, name, allowed=None):
    """Check that a type name is not defined or defined with the given value.

    Args:
      name: str, the name of the type in the type table.
      allowed: optional str, if a type is already defined in the
        typetable, then the existing C++ type for `name` must match this
        value. This only applies if `name` already exists.

    Raises:
      NameError: if the name is not defined, or if it is defined but doesn't
        match the allowed value.
    """
    if name in self._capsules:
      raise NameError('Name "%s" already defined as capsule name.' % name)

    if self._typetable.has_type(name):
      if not allowed:
        raise NameError(
            'Name %r already defined as type %r, but it was expected to '
            'be undefined' % (name, self._typetable.get_last_cpp_type(name)))
      elif self._typetable.get_last_cpp_type(name) != allowed:
        raise NameError(
            'Name %r already defined as type %r, but %r was expected' %
            (name, self._typetable.get_last_cpp_type(name), allowed))

    if name in self._typenames:
      raise NameError('Name "%s" already defined as type alias.' % name)
    if name in self._macros:
      raise NameError('Name "%s" already defined as interface name.' % name)

  def Translate(self, pytd_file):  # pylint: disable=invalid-name
    """Given an open .pytd file, return a CLIF AST ast_pb2.AST protobuffer."""
    pb = ast_pb2.AST()
    pb.source = pytd_file.name
    for hdr in self._scan_includes:
      pb.usertype_includes.append(hdr)
      self._include(0, [hdr], pb, scan_only=True)
    self._parse_preamble(pb)

    self._parse_pytd(pytd_file, pb)

    # Assumed we always want a deterministic output proto. Since dict/set order
    # is not, do sorted() order traversal.
    order = sorted
    for name, fq_name in order(self._names.items()):
      nm = pb.namemaps.add()
      nm.name = name
      nm.fq_name = fq_name
    for pytype, cpp_types  in order(self._typetable.iter_types()):
      tm = pb.typemaps.add()
      tm.lang_type = pytype
      for cpp_type in order(set(cpp_types)):
        tm.cpp_type.append(cpp_type)
    for t in order(self._capsules):
      tm = pb.typemaps.add()
      tm.lang_type = t
      tm.cpp_type.append(self._capsules[t])
    for name, (nargs, src, local) in order(self._macros.items()):
      if local:
        m = pb.macros.add()
        m.name = name
        # Use protocol 0 to keep version independence.
        m.definition = pickle.dumps(
            (sys.hexversion, pytd_parser.version, (nargs, src)), 0)
    ast_manipulations.MoveExtendsOutOfClassesInPlace(pb)
    return pb

  def _parse_preamble(self, pb):
    if self._preamble:
      source = self._preamble
      self._parse_pytd_ast(source, self._ast_from_text(source), pb)

  def _parse_pytd(self, fp, pb):
    """Parse a pytd input file.

    Args:
      fp: an open file for reading.
      pb: output proto to parse into.
    """
    source = fp.read()
    ast = self._ast_from_text(source)
    self._gather_types(ast)  # For forward references.
    self._parse_pytd_ast(source, ast, pb)

  def _parse_pytd_ast(self, source, ast, pb):
    self.source = source  # Save for line number calculation.
    for ir in ast:
      if ir:
        # IR is specific to the parser.
        # IR[0] is a statement name.
        getattr(self, '_'+ir[0])(self.line(ir[1]), ir[2:], pb)
    self.source = None

  def line(self, loc):
    return pytd_parser.LineNum(loc, self.source)

  def _ast_from_text(self, text):
    return pytd_parser.Clif.parseString(text, parseAll=True)

  def _gather_types(self, ast):
    """Populate typetable with fully qualified type names."""
    for ir in ast:
      if ir:
        self._gather_dispatch(ir)

  def _gather_dispatch(self, ast, **kwargs):
    """Given an AST node, dispatch to the appropriate handler function.

    Args:
      ast: pyparsing.ParseResults
      **kwargs: Additional keyword args to pass onto the dispatched-to function.
    """
    ast_type = ast[0]
    # We only visit constructs that might contribute type information
    if ast_type not in ('from', 'namespace', 'class'):
      return
    func_name = '_gather_{}'.format(ast_type)
    func = getattr(self, func_name, None)
    assert func, 'No gather_types function for AST node type {!r}'.format(
        ast_type)
    func(ast, **kwargs)  # pylint: disable=not-callable

  def _gather_from(self, ast):
    """Visit a from-header ast node to gather types."""
    for child in ast[3]:
      self._gather_dispatch(child)

  def _gather_class(self, ast, namespace=None):
    """Visit a class declaration to gather type declarations.

    Args:
      ast: pyparsing.ParseResults
      namespace: Optional[str], the cpp namespace the class is within; this
        is only used by top-level class definitions.
    """
    # The ast name is either:
    # * 1 element: [Foo] from "class Foo"
    # * 2 elements: [CppName, PyName] from "class `CppName` as PyName
    if len(ast.name) not in (1, 2):
      raise ValueError(
          'Class name ast node must be length 1 or 2, got {!r}'.format(
              list(ast.name)))

    if namespace:
      cpp_name = '{}::{}'.format(namespace, ast.name[0])
    else:
      cpp_name = ast.name[0]

    pyname = ast.name[-1]
    self._typetable.set_type(pyname, cpp_name)

    with self._typetable.scope(pyname):
      children = ast[-1]
      for child in children:
        self._gather_dispatch(
            child,
            # Explicitly clear namespace to prevent the namespace from being
            # redundantly and erroneously prepended to nested types. This
            # also mimics the normal parsing behavior.
            namespace=None)

  def _gather_namespace(self, ast):
    """Visit a namespace node for gathering types."""
    namespace = ast[2]
    children = ast[3]
    for child in children:
      self._gather_dispatch(child, namespace=namespace)

  # statement
  #
  # Args:
  #   ln: line number in the .clif file
  #   p: IR subtree (with statement keyword removed)
  #   pb: AST proto for this statement to fill

  def _OPTION(self, ln, p, pb):  # pylint: disable=invalid-name
    """Processing of `OPTION name = value` (go/pyclif#OPTION)."""
    assert len(p) == 2, (ln, p)
    name, value = p
    if name != 'is_extended_from_python':
      raise ValueError('Unknown OPTION name at line %d: %s' % (ln, name))
    if name in pb.options:
      raise ValueError('Duplicate OPTION name at line %d: %s' % (ln, name))
    if value not in ('False', 'True'):
      raise ValueError(
          'Invalid OPTION value at line %d: %s (must be False or True)'
          % (ln, value))
    pb.options[name] = value

  def _interface(self, ln, p, unused_pb=None):
    """'Macro definition' stores a subtree with var placeholders (%0, %1...)."""
    assert len(p) > 2, p
    nargs = len(p) - 2  # 0-name, -1-block, [1:-1]-args
    name = p[0]
    self.check_known_name(name)
    args = {name: pos for pos, name in enumerate(p[:-1])}
    if len(args) != nargs+1:
      raise NameError('all interface args must be different '
                      'at line %d, got %s<%s>' % (ln, name, ', '.join(p[1:-1])))
    src = p[-1]
    if nargs:
      for ast in src:
        if ast[0] == 'func':
          for p in ast.params:
            _subst_type_formal(p, args)
          for p in ast.returns:
            _subst_type_formal(p, args)
        elif ast[0] == 'var':
          _subst_type_formal(ast, args)
        else:
          raise NameError('Only def and var allowed in interface,'
                          ' found "%s" at line %d' % (ast[0], ln))
    self._macros[name] = nargs, src, True

  def _from(self, unused_ln, p, pb):
    """from "full/project/path/cheader.h": BLOCK."""
    assert len(p) == 2, str(p)
    hdr = p[0]
    for s in p[1]:
      if s[0] == 'namespace':
        self._namespace(None, s, pb, hdr)
      elif s[0] == 'staticmethods':
        self._staticmethods(None, s, pb, hdr)
      elif s[0] != 'pass':
        decl = pb.decls.add()
        decl.cpp_file = hdr
        getattr(self, '_'+s[0])(self.line(s[1]), s, decl)

  def _namespace(self, unused_ln, p, pb, hdr):
    """namespace `x::y::z` processing."""
    assert len(p) == 4, str(p)
    ns = 'clif' if p[2] == 'std' else p[2]
    for s in p[-1]:
      if s[0] == 'interface':
        self._interface(self.line(s[1]), s[2:])
      elif s[0] == 'staticmethods':
        self._staticmethods(self.line(s[1]), s, pb, hdr, ns=ns)
      else:
        decl = pb.decls.add()
        decl.cpp_file = hdr
        decl.namespace_ = ns
        getattr(self, '_'+s[0])(self.line(s[1]), s, decl, ns=ns)

  def _staticmethods(self, ln, p, pb, hdr, ns=''):
    """staticmethods from `SomeType` processing."""
    assert len(p) == 4, str(p)
    assert hdr
    if ns and p[2].startswith(':'):
      raise NameError('Invalid reference to global class %s inside namespace %s'
                      ' at line %d' % (p[2], ns, ln))
    cns = ns +  '::' + p[2]
    for s in p[-1]:
      decl = pb.decls.add()
      decl.cpp_file = hdr
      if ns:
        decl.namespace_ = ns
      getattr(self, '_'+s[0])(self.line(s[1]), s, decl, ns=cns)

  def _include(self, unused_ln, p, pb, scan_only=False):
    """from "full/project/path/cheader.h" import *."""
    assert len(p) in (1, 2), p
    hdr = p[0]
    if not scan_only:
      pb.usertype_includes.append(hdr)
    # Scan hdr for new types
    namespace = p[1]+'.' if len(p) > 1 else ''
    for root in self._include_paths:
      try:
        with codecs.open(os.path.join(root, hdr),
                         encoding='utf-8') as include_file:
          pb.usertype_includes.extend(
              _read_include(include_file, hdr, namespace,
                            self._typetable, self._capsules, self._macros,
                            pb.extra_init))
        break
      except IOError:
        pass
    else:
      raise NameError('include "%s" not found' % hdr)

  def _import(self, unused_ln, p, unused_pb):
    """from full.python.path import postprocessor."""
    assert len(p) == 2, str(p)
    n = p[1]
    if n in self._names:
      raise NameError('Name %r already defined' % n)
    self._names[n] = '.'.join(p)

  def _type(self, unused_ln, p, pb):
    """type T = [`postconversion` as] pytype."""
    # typedef alias name(p[0]) = type(p[1])
    assert len(p) == 2, p.dump()
    if p[0] in self._typenames:
      raise NameError('Type %r already defined' % p[0])
    pytype = p[1].name[-1]
    if not self._typetable.has_type(pytype):
      raise NameError('Type %r not defined' % pytype)
    self._typenames[p[0]] = p[1]
    if len(p[1].name) > 1:
      # Save postconversion.
      tm = pb.typemaps.add()
      tm.lang_type = p[0]
      tm.postconversion = p[1].name[0]

  def _use(self, ln, p, unused_pb):
    """use `ctype` as pytype."""
    assert len(p) == 2, p.dump()
    if p[0].endswith('*'):
      raise NameError('Wrap type %s before use' % p[0][:-1])
    if not self.is_pyname_known(p[1]):
      raise NameError('Type %s should be defined before use at line %s'
                      % (p[1], ln))
    self._typetable.add_type(0, p[1], p[0])

  # decl

  def _extract_template_base_name(self, cpp_class_name):
    """Extracts the template name when the class is a renamed C++ template.

    We only want to check for `::` in the class/template name but not in the
    template parameters:
    - "class `Foo<namespace::Type>` as PyFoo" is valid,
    - "class `namespace::Foo` as PyFoo" is not valid,
    - "class `namespace::Foo<Type>` as PyFoo" is not valid.

    Args:
      cpp_class_name: The name of the cpp class, i.e. `Class` or
        `Template<...>`.
    Returns:
      The base name of the template (left of first "<") when
      cpp_class_name is templated, None otherwise.
    """
    parameter_index = cpp_class_name.find('<')
    return None if parameter_index < 0 else cpp_class_name[:parameter_index]

  def _class(self, ln, ast, pb, ns=None):
    """Translate PYTD class IR ast to AST Decl protobuf."""
    assert isinstance(pb, ast_pb2.Decl), repr(pb)
    atln = ' at line %d' % ln
    pb.line_number = ln
    pb.decltype = pb.CLASS
    p = pb.class_
    cpp_name = ast.name[0]  # Save C++ name without FQ.
    is_iterator = ast.name[-1] == '__iter__'
    _set_name(
        p.name,
        ast.name,
        ns,
        allow_fqcppname=is_iterator,
        template_name=self._extract_template_base_name(cpp_name))
    pyname = p.name.native
    self.check_known_name(pyname, p.name.cpp_name)
    decorators = ast.decorators.asList()
    if not is_iterator:
      self._typetable.set_type(pyname, p.name.cpp_name)
      if 'final' in decorators:
        p.final = True
        decorators.remove('final')
      if 'enable_instance_dict' in decorators:
        p.enable_instance_dict = True
        decorators.remove('enable_instance_dict')
      if 'suppress_upcasts' in decorators:
        p.suppress_upcasts = True
        decorators.remove('suppress_upcasts')
      if 'suppress_shared_ptr_const_conversion' in decorators:
        p.suppress_shared_ptr_const_conversion = True
        decorators.remove('suppress_shared_ptr_const_conversion')
    if decorators:
      raise NameError('Unknown class decorator(s)%s: %s'
                      % (atln, ', '.join(decorators)))
    _set_bases(p.bases, ast.bases, self._names, self._typetable)

    # Iterators don't add themselves to the type table (see above), so we can't
    # create a child scope based on them. Not that it matters: __iter__
    # classes aren't allowed to have anything in them.
    if not is_iterator:
      self._typetable.push_scope(pyname)

    if ast.docstring:
      p.docstring = ast.docstring[0][2]

    local_names = set()
    for decl in ast[-1]:
      if decl[0] == 'pass':
        # Pass is a special case as we don't want to add() to the proto.
        if len(ast[-1]) != 1:
          raise SyntaxError('pass must be the only class statement' + atln)
        continue
      line_number = self.line(decl[1])
      if is_iterator:
        if (len(ast[-1]) != 1 or
            decl[0] != 'func' or decl.name[-1] != '__next__'):
          raise SyntaxError('__iter__ class must only def __next__ at line %d'
                            % line_number)
      else:
        if decl[0] == 'implements':
          name = decl[2]
          self._macro_values = [pyname] + decl[3:]
          try:
            nargs, src, _ = self._macros[name]
          except KeyError:
            raise NameError('interface %s not defined' % name + atln)
          if len(self._macro_values) != nargs+1:
            raise NameError('interface %s needs %d args (%d given)'
                            % (name, len(self._macro_values)-1, nargs) + atln)
          for d in src:
            ln = self.line(d[1])
            if d[0] == 'func':
              if not self.unproperty(ln, d, pyname, p.members, local_names):
                _add_uniq(pyname, local_names,
                          self._func(ln, d, p.members.add()))
            elif d[0] == 'var':
              _add_uniq(pyname, local_names, self._var(ln, d, p.members.add()))
            else:
              raise SyntaxError('implements %s contains disallowed %s%s'
                                % (name, d[0], atln))
          self._macro_values = []
          continue
        if decl[0] == 'func' and self.unproperty(
            line_number, decl, pyname, p.members, local_names):
          continue
      name = getattr(self, '_'+decl[0])(line_number, decl, p.members.add())
      _add_uniq(pyname, local_names, name)

    funcs = [m.func for m in p.members if m.decltype == m.FUNC]
    is_sequential = any(f.name.native.endswith('#') for f in funcs)
    if is_sequential and any(f.name.native in _RIGHT_OPS for f in funcs):
      raise NameError("class %s %s can't be sequence and number"
                      ' at the same time' % (p.name.native, atln))
    for f in funcs:
      # Fix ctor name to be the class name.
      if f.name.native == '__init__':
        if (f.name.cpp_name and
            f.name.cpp_name not in [cpp_name, '__init__']):
          print('Arbitrary names (like "{0}") for {1} ctor not allowed.'
                ' Set to {1}'.format(f.name.cpp_name, cpp_name),
                file=sys.stderr)
        f.name.cpp_name = cpp_name
        f.constructor = True
      elif f.name.native == cpp_name:
        raise NameError('Use __init__ to wrap a "%s" constructor'%pyname + atln)
      elif f.name.cpp_name == cpp_name:
        # @add__init__ will reset cpp_name to be empty.
        raise NameError('Use @add__init__ to wrap additional "%s" constructor'
                        '(s).' % pyname + atln)
      elif not f.name.cpp_name:  # An additional ctor.
        f.name.cpp_name = cpp_name
        f.constructor = True

      # Fix 'self' for C++ operator function (implemented out of class).
      elif f.name.native in _RIGHT_OPS:
        if len(f.params) != 1:
          raise ValueError('%s must have only 1 input parameter'
                           % f.name.native + atln)
        f.cpp_opfunction = True  # Request a non-member function.
        self._set_this(f.params.add(), cpp_name, p.name.cpp_name)
      elif '::' in f.name.cpp_name:
        if not f.params:
          f.params.add()
        # else make room for param[0] by shifting 0->1, 1->2 and so on.
        elif len(f.params) == 1:
          f.params.extend([f.params[0]])
        else:
          pcopy = ast_pb2.FuncDecl()
          pcopy.params.extend(f.params)
          del f.params[1:]
          f.params.extend(pcopy.params)
          del pcopy
        f.cpp_opfunction = True  # Request a non-member function.
        self._set_this(f.params[0], cpp_name, p.name.cpp_name)

      # Fix 'item|add__' for a 'sequential' class.
      elif is_sequential and (f.name.native.endswith('item__') or
                              f.name.native.endswith('add__')):
        f.name.native += '#'  # Move '+' to tp_as_sequence slots.

    if not is_iterator:
      self._typetable.pop_scope()
    return pyname

  @staticmethod
  def _set_this(param, py_class_name, cpp_class_name):
    param.name.native = 'self'
    param.name.cpp_name = 'this'
    param.type.lang_type = py_class_name
    param.type.cpp_type = cpp_class_name

  def unproperty(self, ln, ast, class_name, members, known_names):
    """Translate PYTD func IR into VAR getter / setter protobuf.

    Args:
      ln: .clif line number
      ast: func IR
      class_name: Python name of the wrapped C++ class
      members: wrapped C++ class memebers
      known_names: names already defined in a C++ class wrapper
    Returns:
      True if ast is a @getter/@setter func that describes 'unproperty' C++ var.
    Raises:
      ValueError: if @getter or @setter refers to existing var with =property().
    """
    assert ast[0] == 'func', repr(ast)
    getset = ast.decorators.asList()
    try:
      getset.remove(KEEP_GIL_DECORATOR)
      do_not_release_gil = True
    except ValueError:
      do_not_release_gil = False
    if getset not in (['getter'], ['setter']): return False
    ast.decorators[:] = []
    # Convert func to var.
    f = ast_pb2.Decl()
    self._func(ln, ast, f)
    f = f.func
    if do_not_release_gil: f.py_keep_gil = True
    cname = f.name.cpp_name
    pyname = f.name.native
    for m in members:
      if m.decltype == m.VAR and m.var.name.cpp_name == cname:
        if m.var.cpp_get.name.cpp_name:
          raise ValueError("property var can't have @getter / @setter func")
        if m.var.name.native == pyname:
          known_names.discard(m.var.name.native)
        break
    else:
      m = members.add()
      m.line_number = ln
      m.decltype = m.VAR
      m.var.name.cpp_name = cname
    _add_uniq(class_name, known_names, pyname)
    p = m.var
    if getset == ['getter']:
      if len(f.returns) != 1 or f.params:
        raise TypeError('@getter signature must be (self)->T')
      p.type.CopyFrom(f.returns[0].type)
      p.cpp_get.name.native = pyname
    else:
      assert getset == ['setter']
      if len(f.params) != 1 or f.returns:
        raise TypeError('@setter signature must be (self, _:T)')
      p.type.CopyFrom(f.params[0].type)
      p.cpp_set.name.native = pyname
      if not p.cpp_get.name.native:
        # Provide default getter as VARNAME().
        p.cpp_get.name.native = cname
      # Preserve func param varname for the error message (not useful otherwise)
      p.name.native = f.params[0].name.native
    return True

  def _enum(self, ln, ast, pb, ns=None):
    """Translate PYTD enum IR ast to AST Decl protobuf."""
    assert isinstance(pb, ast_pb2.Decl), repr(pb)
    pb.line_number = ln
    pb.decltype = pb.ENUM
    e = pb.enum
    _set_name(e.name, ast.name, ns)
    pyname = e.name.native
    self.check_known_name(pyname)
    self._typetable.set_type(pyname, e.name.cpp_name)
    if len(ast) > 3:
      for rename in ast[-1]:
        _set_name(e.members.add(), rename)
    return pyname

  def _var(self, ln, ast, pb):
    """Translate PYTD var IR ast to AST Decl protobuf."""
    assert isinstance(pb, ast_pb2.Decl), repr(pb)
    pb.line_number = ln
    pb.decltype = pb.VAR
    p = pb.var
    _set_name(p.name, ast.name)
    self.set_type(p.type, ast)
    if ast.getter:
      f = p.cpp_get
      f.name.cpp_name = ast.getter
      self.set_type(f.returns.add().type, ast,
                    lambda x, f=f: _set_keep_gil(f, x))
    if ast.setter:
      f = p.cpp_set
      f.name.cpp_name = ast.setter
      self.set_type(f.params.add().type, ast,
                    lambda x, f=f: _set_keep_gil(f, x))
      f.ignore_return_value = True
    if ast.docstring:
      p.docstring = ast.docstring[0][2]
    decorators = ast.decorators.asList()
    if 'extend' in decorators:
      p.is_extend_variable = True
      decorators.remove('extend')
    return p.name.native

  def _const(self, ln, ast, pb, ns=None):
    """Translate PYTD const IR ast to AST Decl protobuf."""
    assert isinstance(pb, ast_pb2.Decl), repr(pb)
    pb.line_number = ln
    pb.decltype = pb.CONST
    p = pb.const
    _set_name(p.name, ast.name, ns)
    if self.set_type(p.type, ast) == 'str':
      p.type.cpp_type = 'const char *'  # Special case for b/27458244.
    return p.name.native

  def _func(self, ln, ast, pb, ns=None):
    """Translate PYTD def IR ast to AST Decl protobuf."""
    assert isinstance(pb, ast_pb2.Decl), repr(pb)
    pb.line_number = ln
    pb.decltype = pb.FUNC
    f = pb.func
    modified_ast_name = ast.name
    if modified_ast_name[-1] == '__reduce__':
      raise NameError('Please define `__reduce_ex__` instead of `__reduce__`. '
                      'Pickle prefers `__reduce_ex__` over `__reduce__`. '
                      '`__reduce__` is a legacy API and only used if '
                      '`__reduce_ex__` does not exist. See go/pyclif-pickle '
                      'for details.')
    if modified_ast_name[-1] == '__nonzero__':
      raise NameError('Please define `__bool__` instead of `__nonzero__`. '
                      'See b/62796379 for details.')
    _set_name(f.name, _fix_special_names(modified_ast_name), ns,
              allow_fqcppname=True)
    if ast.returns and ast.returns.asList() == [['', [['self']]]]:
      del ast['returns']
      return_self = True
    else:
      return_self = False
    self.set_func(f, ast)
    decorators = ast.decorators.asList()
    if ast.self == 'cls':
      if 'classmethod' not in decorators:
        raise ValueError('Method %s with the first arg cls should be '
                         '@classmethod' % f.name.native)
      if 'virtual' in decorators:
        raise ValueError("Classmethods can't be @virtual")
      f.classmethod = True
      decorators.remove('classmethod')
    elif 'classmethod' in decorators:
      raise ValueError('Method %s with the first arg self should not be '
                       '@classmethod' % f.name.native)
    elif 'virtual' in decorators:
      if ast.self != 'self':
        raise ValueError('@virtual method first arg must be self')
      f.virtual = True
      decorators.remove('virtual')
    if KEEP_GIL_DECORATOR in decorators:
      f.py_keep_gil = True
      decorators.remove(KEEP_GIL_DECORATOR)
    if 'add__init__' in decorators:
      f.name.cpp_name = ''  # A hack to flag an extra ctor.
      decorators.remove('add__init__')
    if 'sequential' in decorators:
      if f.name.native not in ('__getitem__', '__setitem__', '__delitem__',
                               '__add__', '__iadd__',
                               '__mul__', '__imul__'):
        raise NameError('Only __{get/set/del}item__, __*add__, or __*mul__'
                        ' can be @sequential (not %s).' % f.name.native)
      f.name.native += '#'  # A hack to flag a sq_* slot.
      decorators.remove('sequential')
    if 'extend' in decorators:
      f.is_extend_method = True
      decorators.remove('extend')
    if 'non_raising' in decorators:
      f.marked_non_raising = True
      decorators.remove('non_raising')
    if 'return_reference' in decorators:
      f.return_value_policy = ast_pb2.FuncDecl.ReturnValuePolicy.REFERENCE
      decorators.remove('return_reference')
    if '__enter__' in decorators:
      f.name.native = '__enter__@'  # A hack to flag a ctx mgr.
      decorators.remove('__enter__')
    elif f.name.native == '__enter__':
      if f.postproc or f.params or len(f.returns) != 1:
        raise NameError('Use @__enter__ decorator for %s instead of rename'
                        % f.name.cpp_name)
    if '__exit__' in decorators:
      f.name.native = '__exit__@'  # A hack to flag a ctx mgr.
      decorators.remove('__exit__')
    elif f.name.native == '__exit__':
      if (len(f.params) != 3
          or len(f.returns) > 1
          or any(p.type.lang_type != 'object' for p in f.params)):
        raise NameError('Use @__exit__ decorator for %s instead of rename'
                        % f.name.cpp_name)
    elif f.name.native in _IGNORE_RETURN_VALUE:
      f.ignore_return_value = True
      if f.name.native in _INPLACE_OPS:
        if ast.self != 'self':
          raise NameError('Inplace ops must have "self" as the first argument.')
        if not return_self:
          raise NameError('Inplace ops must return "self".')
        if ast.postproc:
          raise ValueError('Inplace ops can\'t have "return Postprocess(...)"')
        f.postproc = '->self'  # '->' indicate special postprocessing.
    if return_self and f.postproc != '->self':
      raise ValueError('Only inplace ops can return "self".')
    if ast.postproc:
      name = ast.postproc[0][0][0]
      try:
        f.postproc = self._names[name]
      except KeyError:
        raise NameError('Should import name "%s" before use.' % name)
    name = f.name.native.rstrip('@#')
    if decorators:
      raise ValueError('Unknown decorator%s for def %s: %s'
                       % ('s' if len(decorators) > 1 else '',
                          name, ', '.join('@'+f for f in decorators)))
    if ast.docstring:
      f.docstring = ast.docstring[0][2]
    return name

  # helpers

  def set_type(self, pb, ast, has_object=lambda x: None):
    """Fill AST Type protobuf from PYTD IR ast."""
    assert isinstance(pb, ast_pb2.Type), repr(pb)
    if ast.callable:
      self.set_func(pb.callable, ast.callable)
      inputs = (a.name.native+':'+a.type.lang_type for a in pb.callable.params)
      inputs = '(%s)' % ', '.join(inputs)
      if len(pb.callable.returns) > 1:
        outputs = (':'+r.type.lang_type for r in pb.callable.returns)
        outputs = '(%s)' % ', '.join(outputs)
      elif pb.callable.returns:
        outputs = pb.callable.returns[0].type.lang_type or 'None'
      else:
        outputs = 'None'
      pb.lang_type = inputs + '->' + outputs
      if pb.lang_type == '()->None':
        # Set any field inside to avoid empty callable message.
        pb.callable.cpp_opfunction = True
      if len(ast.callable) == 3:  # Has an explicit C++ type.
        pb.cpp_type = ast.callable[0]
      # Else fill it after matcher finds the types.
    if ast.named:
      self.set_typename(pb, ast.named)
      if len(ast.named) > 1:
        pb.lang_type += '<%s>' % ', '.join(self.set_type(
            pb.params.add(), t, has_object) for t in ast.named[1:])
        if len(ast.named.name) > 1:  # Has an explicit C++ type.
          pb.cpp_type = ast.named.name[0]
    assert pb.lang_type, 'Parameter AST is not "named" or "callable":\n%r' % ast
    if pb.lang_type == 'object': has_object(True)
    return pb.lang_type

  def set_typename(self, pb, ast):
    """Substitute C++ type based on pytype name."""
    assert isinstance(pb, ast_pb2.Type), repr(pb)
    pytype = ast.name[-1]
    if pytype.startswith('%'):
      assert self._macro_values
      pytype = self._macro_values[int(pytype[1:])]
    if not self.is_pyname_known(pytype):
      raise NameError('Type %s should be defined before use. Did you forget to'
                      ' import a CLIF-generated C++ header?' % pytype)
    pb.lang_type = pytype
    if len(ast.name) > 1:  # Has an explicit C++ type.
      pb.cpp_type = ast.name[0]
    else:
      ctype = self._capsules.get(pytype)
      if ctype:
        pb.cpp_raw_pointer = True
      elif self._typetable.has_type(pytype):
        ctype = self._typetable.get_last_cpp_type(pytype)
      else:
        alias_ir = self._typenames.get(pytype)
        if alias_ir:
          pytype = alias_ir.name[-1]
          assert self._typetable.has_type(pytype), ('alias %s not in typetable'
                                                    % pytype)
          ctype = self._typetable.get_last_cpp_type(pytype)
      assert ctype, 'C++ type for %s not found' % pytype
      pb.cpp_type = ctype

  def set_func(self, pb, ast):
    """Fill AST FuncDecl protobuf from PYTD IR ast."""
    assert isinstance(pb, ast_pb2.FuncDecl), repr(pb)
    arg_names = set()
    must_be_optional = False
    for arg in ast.params:
      pyname = arg.name[-1]
      if pyname in arg_names:
        raise NameError('Name "%s" already used in args.' % pyname)
      arg_names.add(pyname)
      p = pb.params.add()
      _set_name(p.name, arg.name)
      self.set_type(p.type, arg, lambda x, f=pb: _set_keep_gil(f, x))
      if len(arg) > 2:
        p.default_value = arg[2]
        must_be_optional = True
      elif must_be_optional:
        raise ValueError('Arg "%s" (and all after) must be optional because '
                         'arg(s) before it marked optional.')
    for t in ast.returns:
      p = pb.returns.add()
      self.set_type(p.type, t, lambda x, f=pb: _set_keep_gil(f, x))
      if t.name:
        pyname = t.name[-1]
        if pyname in arg_names:
          raise NameError('Name "%s" already used in args.' % pyname)
        arg_names.add(pyname)
        _set_name(p.name, t.name)


class _TypeTable:
  """Manage the Python -> C++ type name mappings.

  Normally, the Python -> C++ mapping is simple: replace '.' with '::'. However,
  there are a variety of special cases:
   * Aliased imports create a Python name with no corresponding C++ type.
   * Class functions can wrap absolutely qualified C++ functions.
   * Mappings added from headers map the Python name to the fully qualified
     C++ type.

  Additionally, there are some basic scoping rules that apply, so the type
  table allows controlling the scope in which lookups occur.
  """

  def __init__(self):
    """Create an instance."""
    self._root = _TypeEntry.create_root_entry()
    self._current_scope = self._root

  @contextlib.contextmanager
  def scope(self, pyname):
    """Context manager for entering and leaving a scope of type names.

    Args:
      pyname: str, Python type name; see `push_scope()`
    Yields:
      None
    """
    try:
      self.push_scope(pyname)
      yield
    finally:
      self.pop_scope()

  def push_scope(self, pyname):
    """Enters a new scope for adding types into under the given `pyname`.

    Instead of calling this manually, prefer to use the `scope()` context
    manager instead.

    Args:
      pyname: str, the name of an existing Python type.
    """
    assert pyname, 'Non-empty pyname is required'
    assert self._current_scope is not None, '_current_scope should be present'
    self._current_scope = self._current_scope.get_nested_type(pyname)

  def pop_scope(self):
    """Leaves the current scope and switches to the parent scope."""
    self._current_scope = self._current_scope.parent

  def set_type(self, pyname, cpp_name):
    """Set a C++ type for a Python type in the current scope.

    This will check that, if `pyname` already exists, that `cpp_name`
    matches the existing value. A mismatch will raise an error.

    This is usually used to add types as they are encountered from type
    definitions in a Clif file.

    Args:
      pyname: str, the Python name of the type. It will be added to the
        current scope. A dotted name is not allowed: the name should
        be the base name for the type in the current scope.
      cpp_name: str, the C++ type name, relative to the current scope, or an
        absolute type name. This _may_ begin with a namespace (MyNs::MyCls),
        but shouldn't include sub-types (MyType::MySubType).
    """
    assert not isinstance(cpp_name, list)
    assert '.' not in pyname
    assert self._current_scope is not None, '_current_scope should be present'
    self._current_scope.set_nested_type(pyname, cpp_name)

  def add_type(self, priority, pyname, cpp_name):
    """Append a CPP type to a Python name in the current scope.

    This makes `cpp_name` the preferred type to use for `pyname`, i.e.,
    last added type wins.

    This is usually used to add imported mappings, e.g., from headers
    or import statements.

    Args:
      priority: int, 2 for prepend, any other value for append.
      pyname: str, the Python name for the type. It can be a dotted name,
        e.g., 'Foo.Bar'. If intermediate types don't exist, empty scopes
        will be created.
      cpp_name: str, the C++ name for the type. If a dotted `pyname` is used,
        then `cpp_name` should reflect the properly qualified C++ name
        for `pyname` relative to the current scope. e.g., if
        pyname=Foo.Bar, then `cpp_name` should likely be 'Foo::Bar'. An absolute
        C++ name can also be used instead (e.g. ::Foo::Bar).
    """
    assert not isinstance(cpp_name, list)
    if '.' in pyname:
      parts = pyname.split('.')
      base_name = parts.pop()
      current = self._current_scope
      for name in parts:
        current = current.add_empty_nested_type(name)
      current.add_nested_type(priority, base_name, cpp_name)
    else:
      self._current_scope.add_nested_type(priority, pyname, cpp_name)

  def get_last_cpp_type(self, pyname):
    """Get the last registered C++ type for a Python type.

    Some Python types have multiple C++ types registered. Most (e.g.,
    a class defined in a .clif file) only have a single type registered.
    For reasons unknown, the last registered type is what gets used
    as the preferred C++ type.

    Args:
      pyname: str, the name of the type. It can be a dotted name, e.g. 'A.B'.

    Returns:
      str, the fully qualified C++ type name that was last mapped to the Python
      type.

    Raises:
      NameError: on unknown Python type.
    """
    parts = pyname.split('.')
    fq_cpp_name_parts = []

    current = self._find_entry(parts[0])
    if not current:
      raise NameError('Unknown Python type: {!r}'.format(pyname))

    for name in parts:
      entry = current.get_nested_type(name)
      cpp_type = entry.get_last_cpp_type()
      if cpp_type:
        # TODO: add a test where an absolute type is registered
        # under a dotted name. Some stubby Response.Code tests failed due to
        # something like that going on. Need a test with a line like
        #   // CLIF use `::Response::Code` as Response.Code
        # An inner type can be mapped to an absolute C++ type, in which case,
        # we don't want to prefix it with the parent. So just reset the parts.
        # Keep iterating, though, since we need to continue down to the
        # final name part.
        if cpp_type.startswith('::'):
          fq_cpp_name_parts = [cpp_type]
        else:
          fq_cpp_name_parts.append(cpp_type)
      current = entry

    full_cpp_type = '::'.join(fq_cpp_name_parts)

    # If types get registered and/or re-joined incorrectly, it can generate
    # names that are malformed, usually by joining two empty names or
    # a relative and absolute name. This helps catch that simple case.
    assert ':::' not in full_cpp_type, 'Malformed C++ typename: {}'.format(
        full_cpp_type)
    return full_cpp_type

  def _find_entry(self, pyname):
    """Search up the scope tree for a Python name."""
    assert '.' not in pyname
    current = self._current_scope
    while current:
      if current.has_nested_type(pyname):
        break
      current = current.parent
    return current

  def has_type(self, pyname):
    """Tells if a Python type is registered.

    Note that it doesn't mean there are C++ types associated with it.

    Args:
      pyname: str, the name of the Python type. It can be a dotted name.

    Returns:
      bool, True if any C++ types are registered, False if not.
    """
    parts = pyname.split('.')

    current = self._find_entry(parts[0])

    if not current:
      return False

    for name in parts:
      if not current.has_nested_type(name):
        return False
      current = current.get_nested_type(name)
    return True

  def find_pyname_for_cpp_type(self, cpp_type):
    """Find the first matching Python type for a C++ type, if any.

    Args:
      cpp_type: str, the c++ type to search for.

    Returns:
      str, the Python type that matches, or empty string if no match.
    """
    for pyname, cpp_types in self.iter_types():
      if cpp_type in cpp_types:
        return pyname
    return ''

  def iter_types(self):
    """Walks through all knowns types and their C++ mappings.

    Yields:
      Tuple[str pyname, list[str] cpp_names], where `pyname` is the
      fully qualified Python name, and `cpp_names` are the fully
      qualified C++ names.
    """
    for entry in self._root.walk_nested_types():
      yield entry

  def __repr__(self):
    # The type table can be pretty big, so format it in a nice way so that
    # its intelligible.
    types = '\n'.join(
        '{:<20} -> {}'.format(*entry) for entry in sorted(self.iter_types()))
    return '_TypeTable(types=\n{types}\n)'.format(types=types)


class _TypeEntry:
  """Type mapping information for use by _TypeTable.

  This is private to _TypeTable; _TypeTable has the public APIs for correctly
  interacting with _TypeEntry data.
  """

  def __init__(self, pyname=None, cpp_name=None, parent=None):
    """Creates an instance: use the class-level helpers instead.

    This constructor is private: use the appropriate create_* methods
    for creating instances to ensure correct creation.

    Args:
      pyname: Optional[str], name of the Python type. Optional for
        the root-level _TypeEntry, otherwise required.
      cpp_name: Optiona[str], name of the corresponding C++ type,
        if any. Additional names may be added later. Root instances
        and "namespace" instances (i.e., names created through an
        aliased import) won't have a C++ type.
      parent: Optional[_TypeEntry], the outer scope for this entry.
        Root level entries don't have it, all others do.
    """
    # Optional[str]
    self._pyname = pyname
    # The C++ type names may be relative to the parent entry, or
    # fully qualified.
    # list[str]
    self._cpp_names = []
    if cpp_name:
      self.add_cpp_type(0, cpp_name)
    # Optional[_TypeEntry]
    self._parent = parent
    # MutableMapping[str py_name, _TypeEntry]
    self._types = {}

  @classmethod
  def create_root_entry(cls):
    """Create a top-level object; only _TypeTable should call this."""
    return cls(None, None)

  def _create_child_entry(self, pyname, cpp_name):
    """Create a child entry of the current entry.

    Args:
      pyname: str, the Python type name, required.
      cpp_name: Optional[str], C++ type name; it may be omitted if
        the child entry is just a "namespace" for containing other types,
        e.g., as part of an aliased import.

    Returns:
      _TypeEntry
    """
    assert pyname, 'Non-empty pyname is required'
    return _TypeEntry(pyname, cpp_name, parent=self)

  @property
  def parent(self):
    return self._parent

  def get_last_cpp_type(self):
    """Get the last registered C++ type, or an empty string if none."""
    return self._cpp_names[-1] if self._cpp_names else ''

  def get_cpp_types(self):
    return self._cpp_names[:]

  def add_cpp_type(self, priority, cpp_name):
    """Add a C++ type to this entry."""
    assert cpp_name
    # NOTE: `cpp_name` may already be in the list, which seems redundant,
    # but is relied upon so that the last use X as Y statement wins.
    if priority == 2:
      self._cpp_names.insert(0, cpp_name)
    else:
      self._cpp_names.append(cpp_name)

  def set_nested_type(self, pyname, cpp_name):
    """Set the C++ type for a Python type, checking for conflicts.

    This is usually used to add a specific mapping for which there is only
    one C++ type, such as a class definition in a clif file -- in such cases,
    there should only be a single C++ type.

    Args:
      pyname: str, the Python name for the type. No dots allowed. If
        the name already exists, then `cpp_name` must match the pre-existing
        entry.
      cpp_name: str, the C++ type name.
    """
    assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                               'meant to use _TypeTable').format(pyname)
    try:
      existing = self._types[pyname]
    except KeyError:
      entry = self._create_child_entry(pyname, cpp_name)
      self._types[pyname] = entry
    else:
      desired_cpp_names = [cpp_name]
      existing_cpp_names = existing._cpp_names  # pylint: disable=protected-access
      if existing_cpp_names != desired_cpp_names:
        raise ValueError(
            'Python type {!r}: existing C++ types {!r} don\'t match desired '
            'types {!r}'.format(pyname, existing_cpp_names, desired_cpp_names))

  def add_nested_type(self, priority, pyname, cpp_name):
    """Append a C++ type to a Python type.

    If the Python type doesn't exist, it will be created.
    If it already exists, then the C++ type will be added.

    This is usually used to add imported mappings, e.g., from headers or
    import statements.

    Args:
      priority: int, 2 for prepend, any other value for append.
      pyname: str, the Python type name, no dots allowed.
      cpp_name: str, the C++ type name.
    """
    assert pyname, 'Non-empty pyname required'
    assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                               'meant to use _TypeTable').format(pyname)
    assert cpp_name, 'Non-empty cpp_name required'
    try:
      existing = self._types[pyname]
    except KeyError:
      entry = self._create_child_entry(pyname, cpp_name)
      self._types[pyname] = entry
    else:
      existing.add_cpp_type(priority, cpp_name)

  def add_empty_nested_type(self, pyname):
    """Create an empty nested type, e.g., to act as a namespace."""
    assert pyname, 'Non-empty pyname required'
    assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                               'meant to use _TypeTable').format(pyname)
    try:
      existing = self._types[pyname]
    except KeyError:
      entry = self._create_child_entry(pyname, None)
      self._types[pyname] = entry
      return entry
    else:
      return existing

  def has_nested_type(self, pyname):
    """Tell if the Python type is present."""
    assert pyname, 'Non-empty pyname required'
    assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                               'meant to use _TypeTable').format(pyname)
    return pyname in self._types

  def get_nested_type(self, pyname):
    """Get the type entry for the Python name.

    Args:
      pyname: str, the Python name, no dots allowed. For dotted-name
        lookup, use the _TypeTable APIs.

    Returns:
      _TypeEntry of the nested type.

    Raises:
      _TypeNotFoundError: if the nested type isn't found.
    """
    assert pyname, 'Non-empty pyname required'
    assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                               'meant to use _TypeTable').format(pyname)
    try:
      child = self._types[pyname]
    except KeyError:
      raise _TypeNotFoundError(pyname)
    return child

  def walk_nested_types(self):
    """Walks over all nested types, recursively.

    Yields:
      Tuple[str pyname, List[str] cpp_names]. `pyname` is the fully
      qualified (relative to this entry) name. `cpp_names` is a list of
      C++ type names; each C++ type is either an absolute name (starts with
      '::'), or fully qualified relative to this entry.
    """
    for pyname, entry in self._types.items():
      cpp_types = entry.get_cpp_types()
      if cpp_types:
        yield pyname, cpp_types

      for child_pyname, child_cpp_types in entry.walk_nested_types():
        if cpp_types:
          prefix = cpp_types[-1]
          child_cpp_types = [
              self._build_cpp_type(prefix, child_cpp_type)
              for child_cpp_type in child_cpp_types
          ]
        yield pyname + '.' + child_pyname, child_cpp_types

  def _build_cpp_type(self, parent_prefix, child_cpp_type):
    if child_cpp_type.startswith('::'):
      return child_cpp_type
    else:
      return '{}::{}'.format(parent_prefix, child_cpp_type)

  def __repr__(self):
    return (
        '_TypeEntry(pyname={pyname!r}, cpp_types={ctypes!r}, '
        'nested_types={nested_names}').format(
            pyname=self._pyname, ctypes=self._cpp_names,
            nested_names=sorted(self._types.keys()))


class _TypeNotFoundError(Exception):
  """Raised when a _TypeEntry doesn't have a requested Python name."""


def _set_bases(pb, ast_bases, names, typetable):
  """Fill AST.ClassDecl bases pb from IR.bases."""
  for b in ast_bases:
    n = b[-1]
    if len(b) != 1:
      raise NameError('Base class must not have a C++ name')
    if n not in names:
      # TODO: Lookup possible 'renames' for bases.
      if not typetable.has_type(n):
        raise NameError('Base class %s not defined' % n)
    base = pb.add()
    base.native = n


def _set_name(pb,
              ast,
              namespace=None,
              allow_fqcppname=False,
              template_name=None):
  """Fill AST Name protobuf from PYTD IR ast.

  Args:
    pb: the AST Name protocol buffer to fill.
    ast: the PYTD IR ast node.
    namespace: the namespace of the c++ type.
    allow_fqcppname: whether to allow fullt qualified namespace.
    template_name: the template base name i.e. `Template` in `Template<...>`. It
      is passed for renamed C++ templated classes only.

  Raises:
    NameError: when the name is not supported.
  """
  assert isinstance(pb, ast_pb2.Name), repr(pb)
  assert ast, repr(ast)
  pb.native = ast[-1]
  if not allow_fqcppname and '::' in (template_name or ast[0]):
    raise NameError(':: not allowed in C++ name for ' + ast[-1])
  if not namespace or ast[0].startswith('::'):  # absolute name
    pb.cpp_name = ast[0]
  else:
    if not namespace.endswith('::'):
      namespace += '::'
    pb.cpp_name = namespace + ast[0]


def _set_keep_gil(f, val):
  f.py_keep_gil = val


def _add_uniq(class_name, names_set, new_name):
  assert new_name, class_name+' has %s' % names_set
  if new_name:
    if new_name in names_set:
      raise NameError('Name "%s" already defined in class %s'
                      % (new_name, class_name))
    names_set.add(new_name)


def _subst_type_formal(ast, from_map):
  """Walk type ast and replace names from_map to %position markers."""
  if ast.callable:
    for p in ast.callable.params:
      _subst_type_formal(p, from_map)
    for p in ast.callable.returns:
      _subst_type_formal(p, from_map)
  if ast.named:
    n = ast.named.name
    if len(ast.named) > 1:
      for t in ast.named[1:]:
        _subst_type_formal(t, from_map)
    else:
      p = n[-1]
      if p in from_map:
        if len(n) > 1:  # Has an explicit C++ type.
          raise NameError('C++ name not allowed in interface parameters (%s)'%p)
        n[-1] = '%' + str(from_map[p])


# Special methods that must return self.
_INPLACE_OPS = frozenset([
    '__iadd__',
    '__iadd__#',  # sq_concat
    '__isub__',
    '__imul__',
    '__imul__#',  # sq_repeat
    '__idiv__',
    '__ifloordiv__',
    '__itruediv__',
    '__imod__',
    '__ipow__',
    '__ilshift__',
    '__irshift__',
    '__iand__',
    '__ixor__',
    '__ior__',
])
# Special methods that don't use returning C++ value, so we can ignore it.
_IGNORE_RETURN_VALUE = frozenset([
    '__setitem__',
    '__delitem__',
    '__setattr__',
    '__delattr__',
] + list(_INPLACE_OPS))

# Python special method name -> C++ operator rename table.
_SPECIAL = {
    '__lt__': 'operator<',
    '__le__': 'operator<=',
    '__gt__': 'operator>',
    '__ge__': 'operator>=',
    '__eq__': 'operator==',
    '__ne__': 'operator!=',
    '__pos__': 'operator+',
    '__add__': 'operator+',
    '__radd__': 'operator+',
    '__iadd__': 'operator+=',
    '__neg__': 'operator-',
    '__sub__': 'operator-',
    '__rsub__': 'operator-',
    '__isub__': 'operator-=',
    '__mul__': 'operator*',
    '__rmul__': 'operator*',
    '__imul__': 'operator*=',
    '__div__': 'operator/',
    '__rdiv__': 'operator/',
    '__idiv__': 'operator/=',
    '__floordiv__': 'operator/',
    '__rfloordiv__': 'operator/',
    '__ifloordiv__': 'operator/=',
    '__truediv__': 'operator/',
    '__rtruediv__': 'operator/',
    '__itruediv__': 'operator/=',
    '__mod__': 'operator%',
    '__rmod__': 'operator%',
    '__imod__': 'operator%=',
    '__lshift__': 'operator<<',
    '__rlshift__': 'operator<<',
    '__ilshift__': 'operator<<=',
    '__rshift__': 'operator>>',
    '__rrshift__': 'operator>>',
    '__irshift__': 'operator>>=',
    '__and__': 'operator&',
    '__rand__': 'operator&',
    '__iand__': 'operator&=',
    '__xor__': 'operator^',
    '__rxor__': 'operator^',
    '__ixor__': 'operator^=',
    '__or__': 'operator|',
    '__ror__': 'operator|',
    '__ior__': 'operator|=',
    '__inv__': 'operator~',
    '__invert__': 'operator~',
    '__call__': 'operator()',
    '__getitem__': 'operator[]',
    '__del__': 'DO_NOT_DECLARE_DTOR',
    '__next__': 'operator*',  # For the "class __iter__: def __next__" case.
    '__int__': 'operator int',
    '__float__': 'operator double',
    # TODO:  fix / remove one of 'operator bool' mapping,
    # so will have only one in the future.
    '__nonzero__': 'operator bool',  # PY2
    '__bool__': 'operator bool',  # PY3
}
_RIGHT_OPS = frozenset([
    # Can only be implemented as free functions, not C++ member functions.
    '__radd__',
    '__rsub__',
    '__rmul__',
    '__rdiv__',
    '__rtruediv__',
    '__rfloordiv__',
    '__rmod__',
    '__rdivmod__',
    '__rpow__',
    '__rlshift__',
    '__rrshift__',
    '__rand__',
    '__ror__',
    '__rxor__',
])
assert _RIGHT_OPS - set(_SPECIAL), frozenset('__r%s__' % op for op in (
    'divmod pow'.split(' ')))


def _fix_special_names(ast_name):
  """Fill "cpp_name" for Python special name if empty."""
  if len(ast_name) == 1:
    pyname = ast_name[0]
    op = _SPECIAL.get(pyname)
    if op:
      return [op, pyname]
  return ast_name
